package opdracht4;

public class SearchTree<K extends Comparable<K>, V> 
{
	protected V value;
	protected K key;
	protected SearchTree<K, V> left, right;
	
	public SearchTree<K, V> createTree() {
		return new SearchTree<K, V>();
	}

	public String toString()
	{
		if(isEmpty()){return "_";}
		return "(" + left + ", ("+ key + ", " + value + "), "+ right + ")";
		// (_, (10, alfa), _)
	}
	public boolean isEmpty()
	{
		return left == null && right == null;
	}
	public int size()
	{
		return isEmpty() ? 0 : 1 + left.size() + right.size();
	}
	public int height()
	{
		return isEmpty() ? 0 : 1 + Math.max( left.height(), right.height());
	}
	public void put(K aKey, V aValue)
	{
		if(isEmpty())
		{
			key   = aKey; 
			value = aValue;
			left  = createTree();
			right = createTree();
		}
		else if(aKey.compareTo(key) < 0)
		{
			left.put(aKey, aValue);
		}
		else if(aKey.compareTo(key) > 0)
		{
			right.put(aKey, aValue);
		}
		else
		{
			value = aValue;
		}
	}
	public boolean containsKey(K aKey)
	{
		if(isEmpty()){return false;}
		if(aKey.compareTo(key) == 0)
		{
			return true;
		}
		if(aKey.compareTo(key) < 0)
		{
			return left.containsKey(aKey);
		}
		if(aKey.compareTo(key) > 0)
		{
			return right.containsKey(aKey);
		}
		else 
			return false;
	}
	
	public boolean contains(V aValue)
	{
		if(isEmpty()){return false;}
		if(aValue.equals(value))
		{
			return true;
		}
		return left.contains(aValue) || right.contains(aValue);
	}
	
	public V get(K aKey)
	{
		if(isEmpty())
		{
			return null;
		}
		else if(aKey.compareTo(key) < 0)
		{
			return left.get(aKey);
		}
		else if(aKey.compareTo(key) > 0)
		{
			return right.get(aKey);
		}
		else
		{
			return value;
		}

	}
	
	protected void removeElement()
	{
		// remove this element
		if(left.isEmpty() && right.isEmpty())
		{
			removeLeaf();
		}
		else if(!left.isEmpty())
		{
			SearchTree<K,V> biggest = left.getBiggest();
			value = biggest.value;
			key   = biggest.key;
			left.remove(key);
		}
		else if(!right.isEmpty())
		{
			SearchTree<K,V> smallest = right.getSmallest();
			value = get(smallest.key);
			key = smallest.key;
			right.remove(key);
		}
	}
	
	public void remove(K aKey)
	{
		if( isEmpty() )
			return;
		else if(aKey.compareTo(key) < 0)
			left.remove(aKey);
		else if(aKey.compareTo(key) > 0)
			right.remove(aKey);
		else
			removeElement();
	}

	protected void removeLeaf()
	{
		key   = null;
		value = null;
		left  = null;
		right = null;
	}

	protected SearchTree<K,V> getSmallest()
	{
		return left.isEmpty() ? this : left.getSmallest();
	}

	protected SearchTree<K,V>  getBiggest()
	{
		return right.isEmpty() ? this : right.getBiggest();
	}
}
